/*
 * MaximizeProfit.cpp
 *	Introduction To Algorithms ,Exercise 15-7
 *  Created on: 2012-5-21
 *      Author: xubin
 */

/*
 * 有i个任务，每个任务运行需要的时间为t(i), 如果能在截止时刻d(i)前完成，则能产生利润p(i)
 * 求怎样安排任务，使得利润总额最大
 * (感觉有点像0-1背包问题）
 */

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

class MaxProfit {
private:
	vector<unsigned> t;
	vector<unsigned> d;
	vector<unsigned> p;
	void debug(vector<unsigned> &v) {
		for (unsigned i = 0; i < v.size(); i++) {
			cout << v[i] << ", ";
		}
		cout << "-----------------------" << endl;
	}
public:
	MaxProfit() {
		static const unsigned time[] = { 1, 2, 1, 2 };
		static const unsigned deadline[] = { 3, 5, 7, 7 };		//!!! deadline要按升序排列
		static const unsigned profit[] = { 3, 2, 2, 3 };
		t.assign(time, time + sizeof(time) / sizeof(time[0]));
		d.assign(deadline, deadline + sizeof(deadline) / sizeof(deadline[0]));
		p.assign(profit, profit + sizeof(profit) / sizeof(profit[0]));
	}

	void solve() {
		unsigned  i = 0;
		unsigned end = *(max_element(d.begin(), d.end()));
		vector<unsigned> opt(end + 1, 0);
		for (i = 1; i <= end; i++) {	//实际上浪费最开始处的那个元素。这样感觉处理起来更好理解点。不用考虑+1或者-1这种问题
			//find all the jobs which satisfies d[i] < i, and get the max value that
			unsigned  j = 0;
			vector<unsigned> v;
			while (d[j] <= i) {
				v.push_back(p[j] + opt[d[j] - t[j]]);
				j++;
			}
			if (max_element(v.begin(), v.end()) == v.end()) {
				opt[i] = 0;
			} else {
				opt[i] = *max_element(v.begin(), v.end());
			}
		}
		debug(opt);
		cout << opt[opt.size() - 1] << endl;
	}
};

int main() {
	MaxProfit m;
	m.solve();
}
